package ans.p131;

import test.Entrance;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * #      131
 * 名称   分割回文串
 * 链接   https://leetcode-cn.com/problems/palindrome-partitioning
 * 题解   [621](https://leetcode-cn.com/problems/palindrome-partitioning/solution)
 * 通过率 72.7%
 * 难道   中等
 */

public class Solution {
    @Entrance
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new LinkedList<>();
        traceback(ans, new ArrayList<>(), s, 0);
        return ans;
    }

    private void traceback(List<List<String>> ans, List<String> list, String s, int index) {
        if (index >= s.length()) {
            ans.add(new ArrayList<>(list));
        }
        for (int i = index; i < s.length(); i++) {
            String substring = s.substring(index, i + 1);
            if (substring.equals(new StringBuilder(substring).reverse().toString())) {
                list.add(substring);
                traceback(ans, list, s, index + substring.length());
                list.remove(list.size() - 1);
            }

        }
    }
}